In computer architecture, a stack is a data structure wherein the value most recently stored is the first value retrieved. The acronym LIFO (last in, first out) describes the action of a stack.
The 80386 32-bit CHMOS microprocessor sold by Intel Corporation of Santa Clara, Calif. is an example of one prior digital computer using a stack. The 80386 microprocessor uses a memory addressing technique called segmentation, wherein the memory space is divided into one or more separate linear regions called segments. A memory address consists of two parts--namely, a segment part that identifies the segment, and an offset part that gives a byte offset within the segment. Both the segment and the offset must be specified for every memory reference. A compiler defines one of the segments as the stack segment.
FIG. 1 illustrates in simplified form the stack memory organization for the prior 80386 microprocessor. On the 80386 microprocessor, the stack grows towards lower addresses, and thus the stack appears to grow downward. In the 80386 microprocessor, the location of the data stored in the stack is defined by the address of the base register plus an offset. On the 80386 microprocessor, the base value contained in a base register plus the offset contained in register ESP identifies the memory location that is the top of the stack. For the 80386 microprocessor, the "top" of the stack is memory location with the lowest address in the stack where data is currently being stored.
The two basic stack operations are push and pop. The push operation adds a new element to the stack, and the pop operation removes the last element pushed. The most recently pushed data value resides in a memory location at the "top" of the stack.
In another prior approach, a register or registers point to the next memory location following the memory location containing data most recently pushed onto the stack.
A stack operation is really two distinct operations in one. For example, a push operation is a move to the external memory and a decrementing of the stack pointer. A pop operation is a move from the external memory and an incrementing of the stack pointer.
In a prior approach to stack operations, a Push register instruction results in the stack pointer being decremented by the word length and then an address being created using the new value. The contents of the register specified are then written to this new address. For a prior Pop register instruction, data is fetched from memory using the value in the stack pointer. The data arriving from memory is written to the register and the stack pointer is incremented. This prior approach is found on the 80386 microprocessor and allows the microprocessor to do a push register instruction in two clocks, and a pop register instruction in four clocks.
One disadvantage to this prior approach for performing stack operations is that it is relatively time consuming, given that multiple clock cycles are required. This prior approach therefore imposes a relative performance penalty, especially in view of the fact that numerous stack push and pop instructions can appear within a given computer program.